from typing import List
import copy


# 39. 组合总和
# 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。
# candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。
# 对于给定的输入，保证和为 target 的不同组合数少于 150 个。
def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
    re = list()
    # 排序，从小到大
    candidates.sort()

    candidates_len = len(candidates)

    def back_track(current_index: int, temp_target: int, current_list: List[int], result_list: List[List[int]]):
        '''
        :param current_num:  当前数
        :param temp_target:  目标数
        :param current_list: 当前累加的集合
        :param result_list:  返回结果
        :return:
        '''

        # 无法找到，因为当前数已经大于 temp_target
        if temp_target < 0:
            return

        # 找到了，添加到结果集里面
        if temp_target == 0:
            deep_copy_list = copy.deepcopy(current_list)
            result_list.append(deep_copy_list)
            return

        # 遍历每一个候选数
        for candidate_index in range(current_index, candidates_len):
            # 当前数
            candidate = candidates[candidate_index]
            # 由于是拍好序的数，可以减少很多种情况
            left_target = temp_target - candidate
            current_list.append(candidate)
            back_track(candidate_index, left_target, current_list, re)
            # 回溯
            current_list.pop()

    back_track(0, target, [], re)

    return re


candidates_1 = [2, 3, 6, 7]
target_1 = 7
result = combinationSum(candidates_1, target_1)
print(f"result:{result}")

candidates_1 = [2, 3, 5]
target_1 = 8
result = combinationSum(candidates_1, target_1)
print(f"result:{result}")

candidates_1 = [2]
target_1 = 1
result = combinationSum(candidates_1, target_1)
print(f"result:{result}")

candidates_1 = [8, 7, 4, 3]
target_1 = 11
result = combinationSum(candidates_1, target_1)
print(f"result:{result}")

candidates_1 = [5, 10, 8, 4, 3, 12, 9]
target_1 = 27
result = combinationSum(candidates_1, target_1)
print(f"result:{result}")

candidates_1 = [6, 8, 12, 5, 9, 3, 4, 11]
target_1 = 31
result = combinationSum(candidates_1, target_1)
print(f"result:{result}")
